package cxydmmszl.chapter04.t072;

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * <li style="color: red;">Prob</li>
 * 表达式得到期望结果的组成种数
 * <li style="color: green;">Desc</li>
 * 给定一个只由 0（假）、1（真）、&（逻辑与）、|（逻辑或）和 ^（异或）五种字符组成的字符串 express，
 * 再给定一个布尔值 desired。返回 express 能有多少种组合方式，可以达到 desired 的结果。
 * <li style="color: green;">Input</li>
 * 输出两行，第一行包含一个只有0、1、&、|和^组成的字符串，其长度小于500；
 * 第二行只有一个布尔值，代表desired。
 * <li style="color: green;">Output</li>
 * 输出一个整数，表示取模后的答案。
 * <li style="color: blue;">Link</li> CD47
 *
 * @author habitplus
 * @since 2021-09-22 20:40
 */
public class Main {
    public static final int MOD = 1000000007;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String express = br.readLine();
        boolean desired = Boolean.parseBoolean(br.readLine());
        br.close();

        int ans = num2(express, desired);
        System.out.println(ans);
    }

    private static int num2(String ex, boolean desired) {
        if (ex == null || ex.length() == 0) {
            return 0;
        }

        char[] chs = ex.toCharArray();

        if (!isValid(chs)) return 0;

        int n = chs.length;

        // 动态规划：
        // 生成两个 n*n 的 二维数组 t 和 f。其中，
        // t[i][j] 表示 express[j...i] 组成 true 的种数，
        // f[i][j] 表示 express[j...i] 组成 false 的种数。
        long[][] t = new long[n][n];
        long[][] f = new long[n][n];
        t[0][0] = chs[0] == '1' ? 1 : 0;
        f[0][0] = chs[0] == '0' ? 1 : 0;

        long tt, tf, ft, ff;
        for (int i = 2; i < n; i += 2) {
            t[i][i] = chs[i] == '1' ? 1 : 0;
            f[i][i] = 1 - t[i][i];
//            f[i][i] = chs[i] == '0' ? 1 : 0;

            for (int j = i - 2; j >= 0; j -= 2) {
                for (int k = j; k < i; k += 2) {
                    tt = t[j][k] * t[k + 2][i] % MOD;
                    tf = t[j][k] * f[k + 2][i] % MOD;
                    ft = f[j][k] * t[k + 2][i] % MOD;
                    ff = f[j][k] * f[k + 2][i] % MOD;
                    if (chs[k + 1] == '&') {
                        t[j][i] += tt;
                        f[j][i] += (ff + tf + ft);
                    } else if (chs[k + 1] == '|') {
                        t[j][i] += (ft + tt + tf);
                        f[j][i] += ff;
                    } else {
                        t[j][i] += ft + tf;
                        f[j][i] += ff + tt;
                    }

                    t[j][i] %= MOD;
                    f[j][i] %= MOD;
                }
            }
        }

        return desired ? (int) t[0][n - 1] : (int) f[0][n - 1];
    }

    private static boolean isValid(char[] ex) {
        if ((ex.length & 1) == 0) {
            return false;
        }

        // 判断奇数位置（从 1 开始）是否全为 1 或 0
        for (int i = 0; i < ex.length; i += 2) {
            if (ex[i] != '1' && ex[i] != '0') {
                return false;
            }
        }

        // 判断偶数位置（从 1 开始）是否全为运算符，即 & 或 | 或 ^
        for (int i = 1; i < ex.length; i += 2) {
            if (ex[i] != '&' && ex[i] != '|' && ex[i] != '^') {
                return false;
            }
        }

        return true;
    }
}
